package com.aqie.medium.structure;

/**
 * 字典树
 */
public class Trie {

    public class TrieNode{
        int value;
        public TrieNode one;
        public TrieNode zero;

        TrieNode(int value) {
            this.value = value;
        }
    }

    public TrieNode root;

    public Trie() {
        this.root = new TrieNode(-1);
    }


    public void insert(int num) {
        TrieNode cur = root;
        int j = 1 << 30;
        for (int i = 0; i < 31; i++) {
            int bit = (j & num);
            if (bit == 0) {
                if (cur.zero == null) {
                    cur.zero = new TrieNode(-1);
                }
                cur = cur.zero;
            } else {
                if (cur.one == null) {
                    cur.one = new TrieNode(-1);
                }
                cur = cur.one;
            }
            j >>= 1;
        }
        cur.value = num;
    }

    public int searchXor(TrieNode one, TrieNode zero) {
        if (one.value != -1 && zero.value != -1) {
            return one.value ^ zero.value;
        }
        if (one.zero == null) {
            return searchXor(one.one, zero.zero != null ? zero.zero : zero.one);
        }
        if (one.one == null) {
            return searchXor(one.zero, zero.one != null ? zero.one : zero.zero);
        }
        if (zero.zero == null) {
            return searchXor(zero.one, one.zero);
        }
        if (zero.one == null) {
            return searchXor(zero.zero, one.one);
        }
        return Math.max(searchXor(one.one, zero.zero), searchXor(one.zero, zero.one));
    }
}
